package primary.code02_Sort;

/**
 * 练习：
 * 打印一个数组的所有逆序对
 */
public class Code03_ReverseOrder {
    private static void printReverseOrder(int[] arr) {
        printReverseOrder(arr, 0, arr.length - 1);
    }

    private static void printReverseOrder(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        printReverseOrder(arr, l, (l + r) / 2);
        printReverseOrder(arr, (l + r) / 2 + 1, r);
        mergeReverseOrderTest(arr, l, (l + r) / 2, r);
    }

    private static void mergeReverseOrder(int[] arr, int l, int m, int r) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        for (int i = 0; i < helper.length; i++) {
            if (p1 > m) {
//                for (int j = p1; j <= m; j++) {
//                    System.out.println(arr[j] + "   ---   " + arr[p2]);
//                } 不产生逆序对
                helper[i] = arr[p2++];
            } else if (p2 > r) {
                helper[i] = arr[p1++];
            } else {
                if (arr[p1] <= arr[p2]) {
                    helper[i] = arr[p1++];
                } else {
                    for (int j = p1; j <= m; j++) {
                        System.out.println(arr[j] + "   ---   " + arr[p2]);
                    }
                    helper[i] = arr[p2++];
                }
            }
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l + j] = helper[j];
        }
    }

    private static void mergeReverseOrderTest(int[] arr, int l, int m, int r) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = m + 1;
        int index = 0;
        while (p1 <= m && p2 <= r) {
            if (arr[p1] > arr[p2]) {
                for (int i = p1; i <= m; i++) {
                    System.out.println(arr[i] + "   ---   " + arr[p2]);
                }
                helper[index++] = arr[p2++];
            } else {
                helper[index++] = arr[p1++];
            }
        }
        while (p1 <= m) {
            helper[index++] = arr[p1++];
        }
        while (p2 <= r) {
            helper[index++] = arr[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            arr[l + i] = helper[i];
        }
    }

    /**
     * 2   ---   1
     * 5   ---   1
     * 3   ---   1
     * 4   ---   1
     * 3   ---   2
     * 4   ---   2
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2, 5, 1};
        printReverseOrder(arr);
    }
}
